package breadthFirstSearch;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class FindLadders {

    private static List<List<String>> ans = new LinkedList<>();

    /**
     * LeetCode T126 单词接龙
     * @param args
     */
    public static void main(String[] args) {
        List<List<String>> ladders = findLadders("hit", "cog", new ArrayList<String>() {{
            this.add("hot");
            this.add("dot");
            this.add("dog");
            this.add("lot");
            this.add("log");
            this.add("cog");
        }});
        System.out.println(ladders);


    }

    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)){
            return ans;
        }
        wordList.add(0, beginWord);
        //wordList.add(endWord);
        int size = wordList.size();
        //将单词列表转化为图
        int[][] graph = new int[size][size];
        for (int i = 0; i < size; i++){
            String word = wordList.get(i);
            for (int j = 0; j < size; j++){
                if (j != i ){
                    boolean edge = isEdge(word, wordList.get(j));
                    if (edge){
                        graph[i][j] = 1;
                    }
                }
            }
        }
        //进行广度优先遍历确定最短序列的长度
        //记录遍历过的节点
        boolean flag = false;
        int minLen = 0;
        boolean[] visited = new boolean[size];
        Queue<GraphNode> queue = new LinkedList<>();
        queue.offer(new GraphNode(beginWord, 0));
        visited[0] = true;
        while (!queue.isEmpty()){
            GraphNode node = queue.poll();
            int index = wordList.indexOf(node.word);
            for (int i = size - 1; i > 0; i--){
                if (graph[index][i] == 1 && !visited[i]){
                    //符合条件收集元素
                    if (wordList.get(i).equals(endWord)){
                        flag = true;
                        minLen = node.depth;
                        break;
                    }
                    queue.offer(new GraphNode(wordList.get(i), node.depth + 1));
                    visited[i] = true;
                }
            }
            if (flag){
                break;
            }
        }
        List<String> trace = new LinkedList<>();
        trace.add(beginWord);
        boolean[] visited1 = new boolean[size];
        visited1[0] = true;
        backtrace(graph, 0, minLen + 2, visited1, wordList, endWord, trace);
        return ans;

    }

    public static void backtrace(int[][] graph, int row, int len, boolean[] visited, List<String> wordList, String endWord, List<String> trace){
        if (trace.size() == len && wordList.get(row) == endWord){
            ans.add(new LinkedList<>(trace));
            return;
        }
        if (trace.size() >= len){
            return;
        }

        for (int i = 1; i < wordList.size(); i++){
            if (graph[row][i] == 1 && !visited[i]){
                trace.add(wordList.get(i));
                visited[i] = true;
                backtrace(graph, i, len, visited, wordList, endWord,trace);
                visited[i] = false;
                trace.remove(trace.size() - 1);
            }
        }

    }

    public static boolean isEdge(String source, String target){
        int count = 0;
        for (int i = 0; i < source.length(); i++){
            if (source.charAt(i) != target.charAt(i)){
                count++;
            }
        }
        return (count == 1);
    }
}
class GraphNode{
    public String word;
    int depth;
    public GraphNode(String word, int depth){
        this.word = word;
        this.depth = depth;
    }
}

